平方求幂（快速幂）：一种高效计算 \(a^n\) 的算法，通过把指数不断“二分”并利用平方运算，将时间复杂度从朴素方法的 \(O(n)\) 降到 \(O(\log n)\)。常用于大整数运算、模幂运算与密码学中。（也常被称为 binary exponentiation。）
/kspnnien ba skwr/
Exponentiation by squaring computes powers in logarithmic time.
平方求幂可以在对数时间内计算幂。
To compute \(a^{10^9} \bmod m\) efficiently, the program uses exponentiation by squaring with modular reduction at each step.
为了高效计算 \(a^{10^9} \bmod m\)，程序使用平方求幂，并在每一步进行取模化简。
该术语由两部分构成：exponentiation（“求幂运算”）+ by squaring（“通过平方”）。它描述的核心思想是：当指数为偶数时，\(a^n=(a^{n/2})^2\)；当指数为奇数时，\(a^n=a\cdot a^{n-1}\)，从而把问题递归/迭代地缩小为更小的指数。这一方法在计算数学与计算机算法传统中由来已久，因其主要操作反复出现“平方”而得名。
Select Language